package com.leetcode.algorithm.y22.m07.w3;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 973. 最接近原点的 K 个点
 * 
 * https://leetcode.cn/problems/k-closest-points-to-origin/
 * 
 * @author jie.deng
 *
 */
class Question0973Solution01 {

	public int[][] kClosest(int[][] points, int k) {
		PriorityQueue<Point> queue = new PriorityQueue<>(Comparator.comparing(Point::getKey));
		for (int i = 0; i < points.length; i++) {
			queue.offer(new Point(points[i]));
		}
		int[][] ans = new int[k][2];
		while (k > 0) {
			ans[k - 1] = queue.poll().point;
			k--;
		}
		return ans;
	}

	class Point {

		public Point(int[] point) {
			super();
			this.point = point;
			this.key = point[0] * point[0] + point[1] * point[1];
		}

		public int[] point;
		public int key;

		public int getKey() {
			return key;
		}

	}

}